/*
 * Copyright 2017 Google Inc. All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef FLATBUFFERS_FLEXBUFFERS_H_
#define FLATBUFFERS_FLEXBUFFERS_H_

#include <map>
// Used to select STL variant.
#include "flatbuffers/base.h"
// We use the basic binary writing functions from the regular FlatBuffers.
#include "flatbuffers/util.h"

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4127)    // C4127: conditional expression is constant
#endif

namespace flexbuffers {

class Reference;
class Map;

// These are used in the lower 2 bits of a type field to determine the size of
// the elements (and or size field) of the item pointed to (e.g. vector).
enum BitWidth
{
    BIT_WIDTH_8 = 0,
    BIT_WIDTH_16 = 1,
    BIT_WIDTH_32 = 2,
    BIT_WIDTH_64 = 3,
};

// These are used as the upper 6 bits of a type field to indicate the actual
// type.
enum Type
{
    TYPE_NULL = 0,
    TYPE_INT = 1,
    TYPE_UINT = 2,
    TYPE_FLOAT = 3,
    // Types above stored inline, types below store an offset.
    TYPE_KEY = 4,
    TYPE_STRING = 5,
    TYPE_INDIRECT_INT = 6,
    TYPE_INDIRECT_UINT = 7,
    TYPE_INDIRECT_FLOAT = 8,
    TYPE_MAP = 9,
    TYPE_VECTOR = 10,    // Untyped.
    TYPE_VECTOR_INT = 11,    // Typed any size (stores no type table).
    TYPE_VECTOR_UINT = 12,
    TYPE_VECTOR_FLOAT = 13,
    TYPE_VECTOR_KEY = 14,
    TYPE_VECTOR_STRING = 15,
    TYPE_VECTOR_INT2 = 16,    // Typed tuple (no type table, no size field).
    TYPE_VECTOR_UINT2 = 17,
    TYPE_VECTOR_FLOAT2 = 18,
    TYPE_VECTOR_INT3 = 19,    // Typed triple (no type table, no size field).
    TYPE_VECTOR_UINT3 = 20,
    TYPE_VECTOR_FLOAT3 = 21,
    TYPE_VECTOR_INT4 = 22,    // Typed quad (no type table, no size field).
    TYPE_VECTOR_UINT4 = 23,
    TYPE_VECTOR_FLOAT4 = 24,
    TYPE_BLOB = 25,
    TYPE_BOOL = 26,
    TYPE_VECTOR_BOOL = 36,    // To Allow the same type of conversion of type to vector type
};

inline bool IsInline(Type t)
{
    return t <= TYPE_FLOAT || t == TYPE_BOOL;
}

inline bool IsTypedVectorElementType(Type t)
{
    return (t >= TYPE_INT && t <= TYPE_STRING) || t == TYPE_BOOL;
}

inline bool IsTypedVector(Type t)
{
    return (t >= TYPE_VECTOR_INT && t <= TYPE_VECTOR_STRING) || t == TYPE_VECTOR_BOOL;
}

inline bool IsFixedTypedVector(Type t)
{
    return t >= TYPE_VECTOR_INT2 && t <= TYPE_VECTOR_FLOAT4;
}

inline Type ToTypedVector(Type t, size_t fixed_len = 0)
{
    assert(IsTypedVectorElementType(t));
    switch(fixed_len)
    {
        case 0:
            return static_cast<Type>(t - TYPE_INT + TYPE_VECTOR_INT);
        case 2:
            return static_cast<Type>(t - TYPE_INT + TYPE_VECTOR_INT2);
        case 3:
            return static_cast<Type>(t - TYPE_INT + TYPE_VECTOR_INT3);
        case 4:
            return static_cast<Type>(t - TYPE_INT + TYPE_VECTOR_INT4);
        default:
            assert(0);
            return TYPE_NULL;
    }
}

inline Type ToTypedVectorElementType(Type t)
{
    assert(IsTypedVector(t));
    return static_cast<Type>(t - TYPE_VECTOR_INT + TYPE_INT);
}

inline Type ToFixedTypedVectorElementType(Type t, uint8_t* len)
{
    assert(IsFixedTypedVector(t));
    auto fixed_type = t - TYPE_VECTOR_INT2;
    *len = static_cast<uint8_t>(fixed_type / 3 + 2);    // 3 types each, starting from length 2.
    return static_cast<Type>(fixed_type % 3 + TYPE_INT);
}

// TODO: implement proper support for 8/16bit floats, or decide not to
// support them.
typedef int16_t half;
typedef int8_t quarter;

// TODO: can we do this without conditionals using intrinsics or inline asm
// on some platforms? Given branch prediction the method below should be
// decently quick, but it is the most frequently executed function.
// We could do an (unaligned) 64-bit read if we ifdef out the platforms for
// which that doesn't work (or where we'd read into un-owned memory).
template <typename R, typename T1, typename T2, typename T4, typename T8>
R ReadSizedScalar(const uint8_t* data, uint8_t byte_width)
{
    return byte_width < 4 ? (byte_width < 2 ? static_cast<R>(flatbuffers::ReadScalar<T1>(data)) :
                                              static_cast<R>(flatbuffers::ReadScalar<T2>(data))) :
                            (byte_width < 8 ? static_cast<R>(flatbuffers::ReadScalar<T4>(data)) :
                                              static_cast<R>(flatbuffers::ReadScalar<T8>(data)));
}

inline int64_t ReadInt64(const uint8_t* data, uint8_t byte_width)
{
    return ReadSizedScalar<int64_t, int8_t, int16_t, int32_t, int64_t>(data, byte_width);
}

inline uint64_t ReadUInt64(const uint8_t* data, uint8_t byte_width)
{
    // This is the "hottest" function (all offset lookups use this), so worth
    // optimizing if possible.
    // TODO: GCC apparently replaces memcpy by a rep movsb, but only if count is a
    // constant, which here it isn't. Test if memcpy is still faster than
    // the conditionals in ReadSizedScalar. Can also use inline asm.
    // clang-format off
  #ifdef _MSC_VER
    uint64_t u = 0;
    __movsb(reinterpret_cast<uint8_t *>(&u),
            reinterpret_cast<const uint8_t *>(data), byte_width);
    return flatbuffers::EndianScalar(u);
  #else
    return ReadSizedScalar<uint64_t, uint8_t, uint16_t, uint32_t, uint64_t>(
             data, byte_width);
  #endif
    // clang-format on
}

inline double ReadDouble(const uint8_t* data, uint8_t byte_width)
{
    return ReadSizedScalar<double, quarter, half, float, double>(data, byte_width);
}

inline const uint8_t* Indirect(const uint8_t* offset, uint8_t byte_width)
{
    return offset - ReadUInt64(offset, byte_width);
}

template <typename T> const uint8_t* Indirect(const uint8_t* offset)
{
    return offset - flatbuffers::ReadScalar<T>(offset);
}

inline BitWidth WidthU(uint64_t u)
{
#define FLATBUFFERS_GET_FIELD_BIT_WIDTH(value, width) \
    {                                                 \
        if(!((u) & ~((1ULL << (width)) - 1ULL)))      \
            return BIT_WIDTH_##width;                 \
    }
    FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 8);
    FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 16);
    FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 32);
#undef FLATBUFFERS_GET_FIELD_BIT_WIDTH
    return BIT_WIDTH_64;
}

inline BitWidth WidthI(int64_t i)
{
    auto u = static_cast<uint64_t>(i) << 1;
    return WidthU(i >= 0 ? u : ~u);
}

inline BitWidth WidthF(double f)
{
    return static_cast<double>(static_cast<float>(f)) == f ? BIT_WIDTH_32 : BIT_WIDTH_64;
}

// Base class of all types below.
// Points into the data buffer and allows access to one type.
class Object
{
public:
    Object(const uint8_t* data, uint8_t byte_width) : data_(data), byte_width_(byte_width) {}

protected:
    const uint8_t* data_;
    uint8_t byte_width_;
};

// Stores size in `byte_width_` bytes before data_ pointer.
class Sized : public Object
{
public:
    Sized(const uint8_t* data, uint8_t byte_width) : Object(data, byte_width) {}
    size_t size() const
    {
        return static_cast<size_t>(ReadUInt64(data_ - byte_width_, byte_width_));
    }
};

class String : public Sized
{
public:
    String(const uint8_t* data, uint8_t byte_width) : Sized(data, byte_width) {}

    size_t length() const
    {
        return size();
    }
    const char* c_str() const
    {
        return reinterpret_cast<const char*>(data_);
    }
    std::string str() const
    {
        return std::string(c_str(), length());
    }

    static String EmptyString()
    {
        static const uint8_t empty_string[] = {0 /*len*/, 0 /*terminator*/};
        return String(empty_string + 1, 1);
    }
    bool IsTheEmptyString() const
    {
        return data_ == EmptyString().data_;
    }
};

class Blob : public Sized
{
public:
    Blob(const uint8_t* data_buf, uint8_t byte_width) : Sized(data_buf, byte_width) {}

    static Blob EmptyBlob()
    {
        static const uint8_t empty_blob[] = {0 /*len*/};
        return Blob(empty_blob + 1, 1);
    }
    bool IsTheEmptyBlob() const
    {
        return data_ == EmptyBlob().data_;
    }
    const uint8_t* data() const
    {
        return data_;
    }
};

class Vector : public Sized
{
public:
    Vector(const uint8_t* data, uint8_t byte_width) : Sized(data, byte_width) {}

    Reference operator[](size_t i) const;

    static Vector EmptyVector()
    {
        static const uint8_t empty_vector[] = {0 /*len*/};
        return Vector(empty_vector + 1, 1);
    }
    bool IsTheEmptyVector() const
    {
        return data_ == EmptyVector().data_;
    }
};

class TypedVector : public Sized
{
public:
    TypedVector(const uint8_t* data, uint8_t byte_width, Type element_type)
        : Sized(data, byte_width), type_(element_type)
    {
    }

    Reference operator[](size_t i) const;

    static TypedVector EmptyTypedVector()
    {
        static const uint8_t empty_typed_vector[] = {0 /*len*/};
        return TypedVector(empty_typed_vector + 1, 1, TYPE_INT);
    }
    bool IsTheEmptyVector() const
    {
        return data_ == TypedVector::EmptyTypedVector().data_;
    }

    Type ElementType()
    {
        return type_;
    }

private:
    Type type_;

    friend Map;
};

class FixedTypedVector : public Object
{
public:
    FixedTypedVector(const uint8_t* data, uint8_t byte_width, Type element_type, uint8_t len)
        : Object(data, byte_width), type_(element_type), len_(len)
    {
    }

    Reference operator[](size_t i) const;

    static FixedTypedVector EmptyFixedTypedVector()
    {
        static const uint8_t fixed_empty_vector[] = {0 /* unused */};
        return FixedTypedVector(fixed_empty_vector, 1, TYPE_INT, 0);
    }
    bool IsTheEmptyFixedTypedVector() const
    {
        return data_ == FixedTypedVector::EmptyFixedTypedVector().data_;
    }

    Type ElementType()
    {
        return type_;
    }
    uint8_t size()
    {
        return len_;
    }

private:
    Type type_;
    uint8_t len_;
};

class Map : public Vector
{
public:
    Map(const uint8_t* data, uint8_t byte_width) : Vector(data, byte_width) {}

    Reference operator[](const char* key) const;
    Reference operator[](const std::string& key) const;

    Vector Values() const
    {
        return Vector(data_, byte_width_);
    }

    TypedVector Keys() const
    {
        const size_t num_prefixed_fields = 3;
        auto keys_offset = data_ - byte_width_ * num_prefixed_fields;
        return TypedVector(Indirect(keys_offset, byte_width_),
                           static_cast<uint8_t>(ReadUInt64(keys_offset + byte_width_, byte_width_)), TYPE_KEY);
    }

    static Map EmptyMap()
    {
        static const uint8_t empty_map[] = {
            0 /*keys_len*/, 0 /*keys_offset*/, 1 /*keys_width*/, 0 /*len*/
        };
        return Map(empty_map + 4, 1);
    }

    bool IsTheEmptyMap() const
    {
        return data_ == EmptyMap().data_;
    }
};

class Reference
{
public:
    Reference(const uint8_t* data, uint8_t parent_width, uint8_t byte_width, Type type)
        : data_(data), parent_width_(parent_width), byte_width_(byte_width), type_(type)
    {
    }

    Reference(const uint8_t* data, uint8_t parent_width, uint8_t packed_type) : data_(data), parent_width_(parent_width)
    {
        byte_width_ = 1U << static_cast<BitWidth>(packed_type & 3);
        type_ = static_cast<Type>(packed_type >> 2);
    }

    Type GetType() const
    {
        return type_;
    }

    bool IsNull() const
    {
        return type_ == TYPE_NULL;
    }
    bool IsBool() const
    {
        return type_ == TYPE_BOOL;
    }
    bool IsInt() const
    {
        return type_ == TYPE_INT || type_ == TYPE_INDIRECT_INT;
    }
    bool IsUInt() const
    {
        return type_ == TYPE_UINT || type_ == TYPE_INDIRECT_UINT;
    }
    bool IsIntOrUint() const
    {
        return IsInt() || IsUInt();
    }
    bool IsFloat() const
    {
        return type_ == TYPE_FLOAT || type_ == TYPE_INDIRECT_FLOAT;
    }
    bool IsNumeric() const
    {
        return IsIntOrUint() || IsFloat();
    }
    bool IsString() const
    {
        return type_ == TYPE_STRING;
    }
    bool IsKey() const
    {
        return type_ == TYPE_KEY;
    }
    bool IsVector() const
    {
        return type_ == TYPE_VECTOR || type_ == TYPE_MAP;
    }
    bool IsMap() const
    {
        return type_ == TYPE_MAP;
    }
    bool IsBlob() const
    {
        return type_ == TYPE_BLOB;
    }

    bool AsBool() const
    {
        return (type_ == TYPE_BOOL ? ReadUInt64(data_, parent_width_) : AsUInt64()) != 0;
    }

    // Reads any type as a int64_t. Never fails, does most sensible conversion.
    // Truncates floats, strings are attempted to be parsed for a number,
    // vectors/maps return their size. Returns 0 if all else fails.
    int64_t AsInt64() const
    {
        if(type_ == TYPE_INT)
        {
            // A fast path for the common case.
            return ReadInt64(data_, parent_width_);
        }
        else
            switch(type_)
            {
                case TYPE_INDIRECT_INT:
                    return ReadInt64(Indirect(), byte_width_);
                case TYPE_UINT:
                    return ReadUInt64(data_, parent_width_);
                case TYPE_INDIRECT_UINT:
                    return ReadUInt64(Indirect(), byte_width_);
                case TYPE_FLOAT:
                    return static_cast<int64_t>(ReadDouble(data_, parent_width_));
                case TYPE_INDIRECT_FLOAT:
                    return static_cast<int64_t>(ReadDouble(Indirect(), byte_width_));
                case TYPE_NULL:
                    return 0;
                case TYPE_STRING:
                    return flatbuffers::StringToInt(AsString().c_str());
                case TYPE_VECTOR:
                    return static_cast<int64_t>(AsVector().size());
                case TYPE_BOOL:
                    return ReadInt64(data_, parent_width_);
                default:
                    // Convert other things to int.
                    return 0;
            }
    }

    // TODO: could specialize these to not use AsInt64() if that saves
    // extension ops in generated code, and use a faster op than ReadInt64.
    int32_t AsInt32() const
    {
        return static_cast<int32_t>(AsInt64());
    }
    int16_t AsInt16() const
    {
        return static_cast<int16_t>(AsInt64());
    }
    int8_t AsInt8() const
    {
        return static_cast<int8_t>(AsInt64());
    }

    uint64_t AsUInt64() const
    {
        if(type_ == TYPE_UINT)
        {
            // A fast path for the common case.
            return ReadUInt64(data_, parent_width_);
        }
        else
            switch(type_)
            {
                case TYPE_INDIRECT_UINT:
                    return ReadUInt64(Indirect(), byte_width_);
                case TYPE_INT:
                    return ReadInt64(data_, parent_width_);
                case TYPE_INDIRECT_INT:
                    return ReadInt64(Indirect(), byte_width_);
                case TYPE_FLOAT:
                    return static_cast<uint64_t>(ReadDouble(data_, parent_width_));
                case TYPE_INDIRECT_FLOAT:
                    return static_cast<uint64_t>(ReadDouble(Indirect(), byte_width_));
                case TYPE_NULL:
                    return 0;
                case TYPE_STRING:
                    return flatbuffers::StringToUInt(AsString().c_str());
                case TYPE_VECTOR:
                    return static_cast<uint64_t>(AsVector().size());
                case TYPE_BOOL:
                    return ReadUInt64(data_, parent_width_);
                default:
                    // Convert other things to uint.
                    return 0;
            }
    }

    uint32_t AsUInt32() const
    {
        return static_cast<uint32_t>(AsUInt64());
    }
    uint16_t AsUInt16() const
    {
        return static_cast<uint16_t>(AsUInt64());
    }
    uint8_t AsUInt8() const
    {
        return static_cast<uint8_t>(AsUInt64());
    }

    double AsDouble() const
    {
        if(type_ == TYPE_FLOAT)
        {
            // A fast path for the common case.
            return ReadDouble(data_, parent_width_);
        }
        else
            switch(type_)
            {
                case TYPE_INDIRECT_FLOAT:
                    return ReadDouble(Indirect(), byte_width_);
                case TYPE_INT:
                    return static_cast<double>(ReadInt64(data_, parent_width_));
                case TYPE_UINT:
                    return static_cast<double>(ReadUInt64(data_, parent_width_));
                case TYPE_INDIRECT_INT:
                    return static_cast<double>(ReadInt64(Indirect(), byte_width_));
                case TYPE_INDIRECT_UINT:
                    return static_cast<double>(ReadUInt64(Indirect(), byte_width_));
                case TYPE_NULL:
                    return 0.0;
                case TYPE_STRING:
                    return strtod(AsString().c_str(), nullptr);
                case TYPE_VECTOR:
                    return static_cast<double>(AsVector().size());
                case TYPE_BOOL:
                    return static_cast<double>(ReadUInt64(data_, parent_width_));
                default:
                    // Convert strings and other things to float.
                    return 0;
            }
    }

    float AsFloat() const
    {
        return static_cast<float>(AsDouble());
    }

    const char* AsKey() const
    {
        if(type_ == TYPE_KEY)
        {
            return reinterpret_cast<const char*>(Indirect());
        }
        else
        {
            return "";
        }
    }

    // This function returns the empty string if you try to read a not-string.
    String AsString() const
    {
        if(type_ == TYPE_STRING)
        {
            return String(Indirect(), byte_width_);
        }
        else
        {
            return String::EmptyString();
        }
    }

    // Unlike AsString(), this will convert any type to a std::string.
    std::string ToString()
    {
        std::string s;
        ToString(false, false, s);
        return s;
    }

    // Convert any type to a JSON-like string. strings_quoted determines if
    // string values at the top level receive "" quotes (inside other values
    // they always do). keys_quoted determines if keys are quoted, at any level.
    // TODO(wvo): add further options to have indentation/newlines.
    void ToString(bool strings_quoted, bool keys_quoted, std::string& s) const
    {
        if(type_ == TYPE_STRING)
        {
            String str(Indirect(), byte_width_);
            if(strings_quoted)
            {
                flatbuffers::EscapeString(str.c_str(), str.length(), &s, true);
            }
            else
            {
                s.append(str.c_str(), str.length());
            }
        }
        else if(IsKey())
        {
            auto str = AsKey();
            if(keys_quoted)
            {
                flatbuffers::EscapeString(str, strlen(str), &s, true);
            }
            else
            {
                s += str;
            }
        }
        else if(IsInt())
        {
            s += flatbuffers::NumToString(AsInt64());
        }
        else if(IsUInt())
        {
            s += flatbuffers::NumToString(AsUInt64());
        }
        else if(IsFloat())
        {
            s += flatbuffers::NumToString(AsDouble());
        }
        else if(IsNull())
        {
            s += "null";
        }
        else if(IsBool())
        {
            s += AsBool() ? "true" : "false";
        }
        else if(IsMap())
        {
            s += "{ ";
            auto m = AsMap();
            auto keys = m.Keys();
            auto vals = m.Values();
            for(size_t i = 0; i < keys.size(); i++)
            {
                keys[i].ToString(true, keys_quoted, s);
                s += ": ";
                vals[i].ToString(true, keys_quoted, s);
                if(i < keys.size() - 1)
                    s += ", ";
            }
            s += " }";
        }
        else if(IsVector())
        {
            s += "[ ";
            auto v = AsVector();
            for(size_t i = 0; i < v.size(); i++)
            {
                v[i].ToString(true, keys_quoted, s);
                if(i < v.size() - 1)
                    s += ", ";
            }
            s += " ]";
        }
        else
        {
            s += "(?)";
        }
    }

    // This function returns the empty blob if you try to read a not-blob.
    // Strings can be viewed as blobs too.
    Blob AsBlob() const
    {
        if(type_ == TYPE_BLOB || type_ == TYPE_STRING)
        {
            return Blob(Indirect(), byte_width_);
        }
        else
        {
            return Blob::EmptyBlob();
        }
    }

    // This function returns the empty vector if you try to read a not-vector.
    // Maps can be viewed as vectors too.
    Vector AsVector() const
    {
        if(type_ == TYPE_VECTOR || type_ == TYPE_MAP)
        {
            return Vector(Indirect(), byte_width_);
        }
        else
        {
            return Vector::EmptyVector();
        }
    }

    TypedVector AsTypedVector() const
    {
        if(IsTypedVector(type_))
        {
            return TypedVector(Indirect(), byte_width_, ToTypedVectorElementType(type_));
        }
        else
        {
            return TypedVector::EmptyTypedVector();
        }
    }

    FixedTypedVector AsFixedTypedVector() const
    {
        if(IsFixedTypedVector(type_))
        {
            uint8_t len = 0;
            auto vtype = ToFixedTypedVectorElementType(type_, &len);
            return FixedTypedVector(Indirect(), byte_width_, vtype, len);
        }
        else
        {
            return FixedTypedVector::EmptyFixedTypedVector();
        }
    }

    Map AsMap() const
    {
        if(type_ == TYPE_MAP)
        {
            return Map(Indirect(), byte_width_);
        }
        else
        {
            return Map::EmptyMap();
        }
    }

    template <typename T> T As();

    // Experimental: Mutation functions.
    // These allow scalars in an already created buffer to be updated in-place.
    // Since by default scalars are stored in the smallest possible space,
    // the new value may not fit, in which case these functions return false.
    // To avoid this, you can construct the values you intend to mutate using
    // Builder::ForceMinimumBitWidth.
    bool MutateInt(int64_t i)
    {
        if(type_ == TYPE_INT)
        {
            return Mutate(data_, i, parent_width_, WidthI(i));
        }
        else if(type_ == TYPE_INDIRECT_INT)
        {
            return Mutate(Indirect(), i, byte_width_, WidthI(i));
        }
        else if(type_ == TYPE_UINT)
        {
            auto u = static_cast<uint64_t>(i);
            return Mutate(data_, u, parent_width_, WidthU(u));
        }
        else if(type_ == TYPE_INDIRECT_UINT)
        {
            auto u = static_cast<uint64_t>(i);
            return Mutate(Indirect(), u, byte_width_, WidthU(u));
        }
        else
        {
            return false;
        }
    }

    bool MutateBool(bool b)
    {
        return type_ == TYPE_BOOL && Mutate(data_, b, parent_width_, BIT_WIDTH_8);
    }

    bool MutateUInt(uint64_t u)
    {
        if(type_ == TYPE_UINT)
        {
            return Mutate(data_, u, parent_width_, WidthU(u));
        }
        else if(type_ == TYPE_INDIRECT_UINT)
        {
            return Mutate(Indirect(), u, byte_width_, WidthU(u));
        }
        else if(type_ == TYPE_INT)
        {
            auto i = static_cast<int64_t>(u);
            return Mutate(data_, i, parent_width_, WidthI(i));
        }
        else if(type_ == TYPE_INDIRECT_INT)
        {
            auto i = static_cast<int64_t>(u);
            return Mutate(Indirect(), i, byte_width_, WidthI(i));
        }
        else
        {
            return false;
        }
    }

    bool MutateFloat(float f)
    {
        if(type_ == TYPE_FLOAT)
        {
            return MutateF(data_, f, parent_width_, BIT_WIDTH_32);
        }
        else if(type_ == TYPE_INDIRECT_FLOAT)
        {
            return MutateF(Indirect(), f, byte_width_, BIT_WIDTH_32);
        }
        else
        {
            return false;
        }
    }

    bool MutateFloat(double d)
    {
        if(type_ == TYPE_FLOAT)
        {
            return MutateF(data_, d, parent_width_, WidthF(d));
        }
        else if(type_ == TYPE_INDIRECT_FLOAT)
        {
            return MutateF(Indirect(), d, byte_width_, WidthF(d));
        }
        else
        {
            return false;
        }
    }

    bool MutateString(const char* str, size_t len)
    {
        auto s = AsString();
        if(s.IsTheEmptyString())
            return false;
        // This is very strict, could allow shorter strings, but that creates
        // garbage.
        if(s.length() != len)
            return false;
        memcpy(const_cast<char*>(s.c_str()), str, len);
        return true;
    }
    bool MutateString(const char* str)
    {
        return MutateString(str, strlen(str));
    }
    bool MutateString(const std::string& str)
    {
        return MutateString(str.data(), str.length());
    }

private:
    const uint8_t* Indirect() const
    {
        return flexbuffers::Indirect(data_, parent_width_);
    }

    template <typename T> bool Mutate(const uint8_t* dest, T t, size_t byte_width, BitWidth value_width)
    {
        auto fits = static_cast<size_t>(static_cast<size_t>(1U) << value_width) <= byte_width;
        if(fits)
        {
            t = flatbuffers::EndianScalar(t);
            memcpy(const_cast<uint8_t*>(dest), &t, byte_width);
        }
        return fits;
    }

    template <typename T> bool MutateF(const uint8_t* dest, T t, size_t byte_width, BitWidth value_width)
    {
        if(byte_width == sizeof(double))
            return Mutate(dest, static_cast<double>(t), byte_width, value_width);
        if(byte_width == sizeof(float))
            return Mutate(dest, static_cast<float>(t), byte_width, value_width);
        assert(false);
        return false;
    }

    const uint8_t* data_;
    uint8_t parent_width_;
    uint8_t byte_width_;
    Type type_;
};

// Template specialization for As().
template <> inline bool Reference::As<bool>()
{
    return AsBool();
}

template <> inline int8_t Reference::As<int8_t>()
{
    return AsInt8();
}
template <> inline int16_t Reference::As<int16_t>()
{
    return AsInt16();
}
template <> inline int32_t Reference::As<int32_t>()
{
    return AsInt32();
}
template <> inline int64_t Reference::As<int64_t>()
{
    return AsInt64();
}

template <> inline uint8_t Reference::As<uint8_t>()
{
    return AsUInt8();
}
template <> inline uint16_t Reference::As<uint16_t>()
{
    return AsUInt16();
}
template <> inline uint32_t Reference::As<uint32_t>()
{
    return AsUInt32();
}
template <> inline uint64_t Reference::As<uint64_t>()
{
    return AsUInt64();
}

template <> inline double Reference::As<double>()
{
    return AsDouble();
}
template <> inline float Reference::As<float>()
{
    return AsFloat();
}

template <> inline String Reference::As<String>()
{
    return AsString();
}
template <> inline std::string Reference::As<std::string>()
{
    return AsString().str();
}

template <> inline Blob Reference::As<Blob>()
{
    return AsBlob();
}
template <> inline Vector Reference::As<Vector>()
{
    return AsVector();
}
template <> inline TypedVector Reference::As<TypedVector>()
{
    return AsTypedVector();
}
template <> inline FixedTypedVector Reference::As<FixedTypedVector>()
{
    return AsFixedTypedVector();
}
template <> inline Map Reference::As<Map>()
{
    return AsMap();
}

inline uint8_t PackedType(BitWidth bit_width, Type type)
{
    return static_cast<uint8_t>(bit_width | (type << 2));
}

inline uint8_t NullPackedType()
{
    return PackedType(BIT_WIDTH_8, TYPE_NULL);
}

// Vector accessors.
// Note: if you try to access outside of bounds, you get a Null value back
// instead. Normally this would be an assert, but since this is "dynamically
// typed" data, you may not want that (someone sends you a 2d vector and you
// wanted 3d).
// The Null converts seamlessly into a default value for any other type.
// TODO(wvo): Could introduce an #ifdef that makes this into an assert?
inline Reference Vector::operator[](size_t i) const
{
    auto len = size();
    if(i >= len)
        return Reference(nullptr, 1, NullPackedType());
    auto packed_type = (data_ + len * byte_width_)[i];
    auto elem = data_ + i * byte_width_;
    return Reference(elem, byte_width_, packed_type);
}

inline Reference TypedVector::operator[](size_t i) const
{
    auto len = size();
    if(i >= len)
        return Reference(nullptr, 1, NullPackedType());
    auto elem = data_ + i * byte_width_;
    return Reference(elem, byte_width_, 1, type_);
}

inline Reference FixedTypedVector::operator[](size_t i) const
{
    if(i >= len_)
        return Reference(nullptr, 1, NullPackedType());
    auto elem = data_ + i * byte_width_;
    return Reference(elem, byte_width_, 1, type_);
}

template <typename T> int KeyCompare(const void* key, const void* elem)
{
    auto str_elem = reinterpret_cast<const char*>(Indirect<T>(reinterpret_cast<const uint8_t*>(elem)));
    auto skey = reinterpret_cast<const char*>(key);
    return strcmp(skey, str_elem);
}

inline Reference Map::operator[](const char* key) const
{
    auto keys = Keys();
    // We can't pass keys.byte_width_ to the comparison function, so we have
    // to pick the right one ahead of time.
    int (*comp)(const void*, const void*) = nullptr;
    switch(keys.byte_width_)
    {
        case 1:
            comp = KeyCompare<uint8_t>;
            break;
        case 2:
            comp = KeyCompare<uint16_t>;
            break;
        case 4:
            comp = KeyCompare<uint32_t>;
            break;
        case 8:
            comp = KeyCompare<uint64_t>;
            break;
    }
    auto res = std::bsearch(key, keys.data_, keys.size(), keys.byte_width_, comp);
    if(!res)
        return Reference(nullptr, 1, NullPackedType());
    auto i = (reinterpret_cast<uint8_t*>(res) - keys.data_) / keys.byte_width_;
    return (*static_cast<const Vector*>(this))[i];
}

inline Reference Map::operator[](const std::string& key) const
{
    return (*this)[key.c_str()];
}

inline Reference GetRoot(const uint8_t* buffer, size_t size)
{
    // See Finish() below for the serialization counterpart of this.
    // The root starts at the end of the buffer, so we parse backwards from there.
    auto end = buffer + size;
    auto byte_width = *--end;
    auto packed_type = *--end;
    end -= byte_width;    // The root data item.
    return Reference(end, byte_width, packed_type);
}

inline Reference GetRoot(const std::vector<uint8_t>& buffer)
{
    return GetRoot(flatbuffers::vector_data(buffer), buffer.size());
}

// Flags that configure how the Builder behaves.
// The "Share" flags determine if the Builder automatically tries to pool
// this type. Pooling can reduce the size of serialized data if there are
// multiple maps of the same kind, at the expense of slightly slower
// serialization (the cost of lookups) and more memory use (std::set).
// By default this is on for keys, but off for strings.
// Turn keys off if you have e.g. only one map.
// Turn strings on if you expect many non-unique string values.
// Additionally, sharing key vectors can save space if you have maps with
// identical field populations.
enum BuilderFlag
{
    BUILDER_FLAG_NONE = 0,
    BUILDER_FLAG_SHARE_KEYS = 1,
    BUILDER_FLAG_SHARE_STRINGS = 2,
    BUILDER_FLAG_SHARE_KEYS_AND_STRINGS = 3,
    BUILDER_FLAG_SHARE_KEY_VECTORS = 4,
    BUILDER_FLAG_SHARE_ALL = 7,
};

class Builder FLATBUFFERS_FINAL_CLASS
{
public:
    Builder(size_t initial_size = 256, BuilderFlag flags = BUILDER_FLAG_SHARE_KEYS)
        : buf_(initial_size), finished_(false), flags_(flags), force_min_bit_width_(BIT_WIDTH_8),
          key_pool(KeyOffsetCompare(buf_)), string_pool(StringOffsetCompare(buf_))
    {
        buf_.clear();
    }

    /// @brief Get the serialized buffer (after you call `Finish()`).
    /// @return Returns a vector owned by this class.
    const std::vector<uint8_t>& GetBuffer() const
    {
        Finished();
        return buf_;
    }

    // Size of the buffer. Does not include unfinished values.
    size_t GetSize() const
    {
        return buf_.size();
    }

    // Reset all state so we can re-use the buffer.
    void Clear()
    {
        buf_.clear();
        stack_.clear();
        finished_ = false;
        // flags_ remains as-is;
        force_min_bit_width_ = BIT_WIDTH_8;
        key_pool.clear();
        string_pool.clear();
    }

    // All value constructing functions below have two versions: one that
    // takes a key (for placement inside a map) and one that doesn't (for inside
    // vectors and elsewhere).

    void Null()
    {
        stack_.push_back(Value());
    }
    void Null(const char* key)
    {
        Key(key);
        Null();
    }

    void Int(int64_t i)
    {
        stack_.push_back(Value(i, TYPE_INT, WidthI(i)));
    }
    void Int(const char* key, int64_t i)
    {
        Key(key);
        Int(i);
    }

    void UInt(uint64_t u)
    {
        stack_.push_back(Value(u, TYPE_UINT, WidthU(u)));
    }
    void UInt(const char* key, uint64_t u)
    {
        Key(key);
        Int(u);
    }

    void Float(float f)
    {
        stack_.push_back(Value(f));
    }
    void Float(const char* key, float f)
    {
        Key(key);
        Float(f);
    }

    void Double(double f)
    {
        stack_.push_back(Value(f));
    }
    void Double(const char* key, double d)
    {
        Key(key);
        Double(d);
    }

    void Bool(bool b)
    {
        stack_.push_back(Value(b));
    }
    void Bool(const char* key, bool b)
    {
        Key(key);
        Bool(b);
    }

    void IndirectInt(int64_t i)
    {
        PushIndirect(i, TYPE_INDIRECT_INT, WidthI(i));
    }
    void IndirectInt(const char* key, int64_t i)
    {
        Key(key);
        IndirectInt(i);
    }

    void IndirectUInt(uint64_t u)
    {
        PushIndirect(u, TYPE_INDIRECT_UINT, WidthU(u));
    }
    void IndirectUInt(const char* key, uint64_t u)
    {
        Key(key);
        IndirectUInt(u);
    }

    void IndirectFloat(float f)
    {
        PushIndirect(f, TYPE_INDIRECT_FLOAT, BIT_WIDTH_32);
    }
    void IndirectFloat(const char* key, float f)
    {
        Key(key);
        IndirectFloat(f);
    }

    void IndirectDouble(double f)
    {
        PushIndirect(f, TYPE_INDIRECT_FLOAT, WidthF(f));
    }
    void IndirectDouble(const char* key, double d)
    {
        Key(key);
        IndirectDouble(d);
    }

    size_t Key(const char* str, size_t len)
    {
        auto sloc = buf_.size();
        WriteBytes(str, len + 1);
        if(flags_ & BUILDER_FLAG_SHARE_KEYS)
        {
            auto it = key_pool.find(sloc);
            if(it != key_pool.end())
            {
                // Already in the buffer. Remove key we just serialized, and use
                // existing offset instead.
                buf_.resize(sloc);
                sloc = *it;
            }
            else
            {
                key_pool.insert(sloc);
            }
        }
        stack_.push_back(Value(static_cast<uint64_t>(sloc), TYPE_KEY, BIT_WIDTH_8));
        return sloc;
    }

    size_t Key(const char* str)
    {
        return Key(str, strlen(str));
    }
    size_t Key(const std::string& str)
    {
        return Key(str.c_str(), str.size());
    }

    size_t String(const char* str, size_t len)
    {
        auto reset_to = buf_.size();
        auto sloc = CreateBlob(str, len, 1, TYPE_STRING);
        if(flags_ & BUILDER_FLAG_SHARE_STRINGS)
        {
            StringOffset so(sloc, len);
            auto it = string_pool.find(so);
            if(it != string_pool.end())
            {
                // Already in the buffer. Remove string we just serialized, and use
                // existing offset instead.
                buf_.resize(reset_to);
                sloc = it->first;
                stack_.back().u_ = sloc;
            }
            else
            {
                string_pool.insert(so);
            }
        }
        return sloc;
    }
    size_t String(const char* str)
    {
        return String(str, strlen(str));
    }
    size_t String(const std::string& str)
    {
        return String(str.c_str(), str.size());
    }
    void String(const flexbuffers::String& str)
    {
        String(str.c_str(), str.length());
    }

    void String(const char* key, const char* str)
    {
        Key(key);
        String(str);
    }
    void String(const char* key, const std::string& str)
    {
        Key(key);
        String(str);
    }
    void String(const char* key, const flexbuffers::String& str)
    {
        Key(key);
        String(str);
    }

    size_t Blob(const void* data, size_t len)
    {
        return CreateBlob(data, len, 0, TYPE_BLOB);
    }
    size_t Blob(const std::vector<uint8_t>& v)
    {
        return CreateBlob(flatbuffers::vector_data(v), v.size(), 0, TYPE_BLOB);
    }

    // TODO(wvo): support all the FlexBuffer types (like flexbuffers::String),
    // e.g. Vector etc. Also in overloaded versions.
    // Also some FlatBuffers types?

    size_t StartVector()
    {
        return stack_.size();
    }
    size_t StartVector(const char* key)
    {
        Key(key);
        return stack_.size();
    }
    size_t StartMap()
    {
        return stack_.size();
    }
    size_t StartMap(const char* key)
    {
        Key(key);
        return stack_.size();
    }

    // TODO(wvo): allow this to specify an aligment greater than the natural
    // alignment.
    size_t EndVector(size_t start, bool typed, bool fixed)
    {
        auto vec = CreateVector(start, stack_.size() - start, 1, typed, fixed);
        // Remove temp elements and return vector.
        stack_.resize(start);
        stack_.push_back(vec);
        return static_cast<size_t>(vec.u_);
    }

    size_t EndMap(size_t start)
    {
        // We should have interleaved keys and values on the stack.
        // Make sure it is an even number:
        auto len = stack_.size() - start;
        assert(!(len & 1));
        len /= 2;
        // Make sure keys are all strings:
        for(auto key = start; key < stack_.size(); key += 2)
        {
            assert(stack_[key].type_ == TYPE_KEY);
        }
        // Now sort values, so later we can do a binary seach lookup.
        // We want to sort 2 array elements at a time.
        struct TwoValue
        {
            Value key;
            Value val;
        };
        // TODO(wvo): strict aliasing?
        // TODO(wvo): allow the caller to indicate the data is already sorted
        // for maximum efficiency? With an assert to check sortedness to make sure
        // we're not breaking binary search.
        // Or, we can track if the map is sorted as keys are added which would be
        // be quite cheap (cheaper than checking it here), so we can skip this
        // step automatically when appliccable, and encourage people to write in
        // sorted fashion.
        // std::sort is typically already a lot faster on sorted data though.
        auto dict = reinterpret_cast<TwoValue*>(flatbuffers::vector_data(stack_) + start);
        std::sort(dict, dict + len, [&](const TwoValue& a, const TwoValue& b) -> bool {
            auto as = reinterpret_cast<const char*>(flatbuffers::vector_data(buf_) + a.key.u_);
            auto bs = reinterpret_cast<const char*>(flatbuffers::vector_data(buf_) + b.key.u_);
            auto comp = strcmp(as, bs);
            // If this assertion hits, you've added two keys with the same
            // value to this map.
            // TODO: Have to check for pointer equality, as some sort
            // implementation apparently call this function with the same
            // element?? Why?
            assert(comp || &a == &b);
            return comp < 0;
        });
        // First create a vector out of all keys.
        // TODO(wvo): if kBuilderFlagShareKeyVectors is true, see if we can share
        // the first vector.
        auto keys = CreateVector(start, len, 2, true, false);
        auto vec = CreateVector(start + 1, len, 2, false, false, &keys);
        // Remove temp elements and return map.
        stack_.resize(start);
        stack_.push_back(vec);
        return static_cast<size_t>(vec.u_);
    }

    template <typename F> size_t Vector(F f)
    {
        auto start = StartVector();
        f();
        return EndVector(start, false, false);
    }
    template <typename F, typename T> size_t Vector(F f, T& state)
    {
        auto start = StartVector();
        f(state);
        return EndVector(start, false, false);
    }
    template <typename F> size_t Vector(const char* key, F f)
    {
        auto start = StartVector(key);
        f();
        return EndVector(start, false, false);
    }
    template <typename F, typename T> size_t Vector(const char* key, F f, T& state)
    {
        auto start = StartVector(key);
        f(state);
        return EndVector(start, false, false);
    }

    template <typename T> void Vector(const T* elems, size_t len)
    {
        if(flatbuffers::is_scalar<T>::value)
        {
            // This path should be a lot quicker and use less space.
            ScalarVector(elems, len, false);
        }
        else
        {
            auto start = StartVector();
            for(size_t i = 0; i < len; i++)
                Add(elems[i]);
            EndVector(start, false, false);
        }
    }
    template <typename T> void Vector(const char* key, const T* elems, size_t len)
    {
        Key(key);
        Vector(elems, len);
    }
    template <typename T> void Vector(const std::vector<T>& vec)
    {
        Vector(flatbuffers::vector_data(vec), vec.size());
    }

    template <typename F> size_t TypedVector(F f)
    {
        auto start = StartVector();
        f();
        return EndVector(start, true, false);
    }
    template <typename F, typename T> size_t TypedVector(F f, T& state)
    {
        auto start = StartVector();
        f(state);
        return EndVector(start, true, false);
    }
    template <typename F> size_t TypedVector(const char* key, F f)
    {
        auto start = StartVector(key);
        f();
        return EndVector(start, true, false);
    }
    template <typename F, typename T> size_t TypedVector(const char* key, F f, T& state)
    {
        auto start = StartVector(key);
        f(state);
        return EndVector(start, true, false);
    }

    template <typename T> size_t FixedTypedVector(const T* elems, size_t len)
    {
        // We only support a few fixed vector lengths. Anything bigger use a
        // regular typed vector.
        assert(len >= 2 && len <= 4);
        // And only scalar values.
        assert(flatbuffers::is_scalar<T>::value);
        return ScalarVector(elems, len, true);
    }

    template <typename T> size_t FixedTypedVector(const char* key, const T* elems, size_t len)
    {
        Key(key);
        return FixedTypedVector(elems, len);
    }

    template <typename F> size_t Map(F f)
    {
        auto start = StartMap();
        f();
        return EndMap(start);
    }
    template <typename F, typename T> size_t Map(F f, T& state)
    {
        auto start = StartMap();
        f(state);
        return EndMap(start);
    }
    template <typename F> size_t Map(const char* key, F f)
    {
        auto start = StartMap(key);
        f();
        return EndMap(start);
    }
    template <typename F, typename T> size_t Map(const char* key, F f, T& state)
    {
        auto start = StartMap(key);
        f(state);
        return EndMap(start);
    }
    template <typename T> void Map(const std::map<std::string, T>& map)
    {
        auto start = StartMap();
        for(auto it = map.begin(); it != map.end(); ++it)
            Add(it->first.c_str(), it->second);
        EndMap(start);
    }

    // Overloaded Add that tries to call the correct function above.
    void Add(int8_t i)
    {
        Int(i);
    }
    void Add(int16_t i)
    {
        Int(i);
    }
    void Add(int32_t i)
    {
        Int(i);
    }
    void Add(int64_t i)
    {
        Int(i);
    }
    void Add(uint8_t u)
    {
        UInt(u);
    }
    void Add(uint16_t u)
    {
        UInt(u);
    }
    void Add(uint32_t u)
    {
        UInt(u);
    }
    void Add(uint64_t u)
    {
        UInt(u);
    }
    void Add(float f)
    {
        Float(f);
    }
    void Add(double d)
    {
        Double(d);
    }
    void Add(bool b)
    {
        Bool(b);
    }
    void Add(const char* str)
    {
        String(str);
    }
    void Add(const std::string& str)
    {
        String(str);
    }
    void Add(const flexbuffers::String& str)
    {
        String(str);
    }

    template <typename T> void Add(const std::vector<T>& vec)
    {
        Vector(vec);
    }

    template <typename T> void Add(const char* key, const T& t)
    {
        Key(key);
        Add(t);
    }

    template <typename T> void Add(const std::map<std::string, T>& map)
    {
        Map(map);
    }

    template <typename T> void operator+=(const T& t)
    {
        Add(t);
    }

    // This function is useful in combination with the Mutate* functions above.
    // It forces elements of vectors and maps to have a minimum size, such that
    // they can later be updated without failing.
    // Call with no arguments to reset.
    void ForceMinimumBitWidth(BitWidth bw = BIT_WIDTH_8)
    {
        force_min_bit_width_ = bw;
    }

    void Finish()
    {
        // If you hit this assert, you likely have objects that were never included
        // in a parent. You need to have exactly one root to finish a buffer.
        // Check your Start/End calls are matched, and all objects are inside
        // some other object.
        assert(stack_.size() == 1);

        // Write root value.
        auto byte_width = Align(stack_[0].ElemWidth(buf_.size(), 0));
        WriteAny(stack_[0], byte_width);
        // Write root type.
        Write(stack_[0].StoredPackedType(), 1);
        // Write root size. Normally determined by parent, but root has no parent :)
        Write(byte_width, 1);

        finished_ = true;
    }

private:
    void Finished() const
    {
        // If you get this assert, you're attempting to get access a buffer
        // which hasn't been finished yet. Be sure to call
        // Builder::Finish with your root object.
        assert(finished_);
    }

    // Align to prepare for writing a scalar with a certain size.
    uint8_t Align(BitWidth alignment)
    {
        auto byte_width = 1U << alignment;
        buf_.insert(buf_.end(), flatbuffers::PaddingBytes(buf_.size(), byte_width), 0);
        return static_cast<uint8_t>(byte_width);
    }

    void WriteBytes(const void* val, size_t size)
    {
        buf_.insert(buf_.end(), reinterpret_cast<const uint8_t*>(val), reinterpret_cast<const uint8_t*>(val) + size);
    }

    template <typename T> void Write(T val, size_t byte_width)
    {
        assert(sizeof(T) >= byte_width);
        val = flatbuffers::EndianScalar(val);
        WriteBytes(&val, byte_width);
    }

    void WriteDouble(double f, uint8_t byte_width)
    {
        switch(byte_width)
        {
            case 8:
                Write(f, byte_width);
                break;
            case 4:
                Write(static_cast<float>(f), byte_width);
                break;
            // case 2: Write(static_cast<half>(f), byte_width); break;
            // case 1: Write(static_cast<quarter>(f), byte_width); break;
            default:
                assert(0);
        }
    }

    void WriteOffset(uint64_t o, uint8_t byte_width)
    {
        auto reloff = buf_.size() - o;
        assert(byte_width == 8 || reloff < 1ULL << (byte_width * 8));
        Write(reloff, byte_width);
    }

    template <typename T> void PushIndirect(T val, Type type, BitWidth bit_width)
    {
        auto byte_width = Align(bit_width);
        auto iloc = buf_.size();
        Write(val, byte_width);
        stack_.push_back(Value(static_cast<uint64_t>(iloc), type, bit_width));
    }

    static BitWidth WidthB(size_t byte_width)
    {
        switch(byte_width)
        {
            case 1:
                return BIT_WIDTH_8;
            case 2:
                return BIT_WIDTH_16;
            case 4:
                return BIT_WIDTH_32;
            case 8:
                return BIT_WIDTH_64;
            default:
                assert(false);
                return BIT_WIDTH_64;
        }
    }

    template <typename T> static Type GetScalarType()
    {
        assert(flatbuffers::is_scalar<T>::value);
        return flatbuffers::is_floating_point<T>::value ?
                   TYPE_FLOAT :
                   flatbuffers::is_same<T, bool>::value ? TYPE_BOOL :
                                                          (flatbuffers::is_unsigned<T>::value ? TYPE_UINT : TYPE_INT);
    }

    struct Value
    {
        union
        {
            int64_t i_;
            uint64_t u_;
            double f_;
        };

        Type type_;

        // For scalars: of itself, for vector: of its elements, for string: length.
        BitWidth min_bit_width_;

        Value() : i_(0), type_(TYPE_NULL), min_bit_width_(BIT_WIDTH_8) {}

        Value(bool b) : u_(static_cast<uint64_t>(b)), type_(TYPE_BOOL), min_bit_width_(BIT_WIDTH_8) {}

        Value(int64_t i, Type t, BitWidth bw) : i_(i), type_(t), min_bit_width_(bw) {}
        Value(uint64_t u, Type t, BitWidth bw) : u_(u), type_(t), min_bit_width_(bw) {}

        Value(float f) : f_(f), type_(TYPE_FLOAT), min_bit_width_(BIT_WIDTH_32) {}
        Value(double f) : f_(f), type_(TYPE_FLOAT), min_bit_width_(WidthF(f)) {}

        uint8_t StoredPackedType(BitWidth parent_bit_width_ = BIT_WIDTH_8) const
        {
            return PackedType(StoredWidth(parent_bit_width_), type_);
        }

        BitWidth ElemWidth(size_t buf_size, size_t elem_index) const
        {
            if(IsInline(type_))
            {
                return min_bit_width_;
            }
            else
            {
                // We have an absolute offset, but want to store a relative offset
                // elem_index elements beyond the current buffer end. Since whether
                // the relative offset fits in a certain byte_width depends on
                // the size of the elements before it (and their alignment), we have
                // to test for each size in turn.
                for(size_t byte_width = 1; byte_width <= sizeof(flatbuffers::largest_scalar_t); byte_width *= 2)
                {
                    // Where are we going to write this offset?
                    auto offset_loc =
                        buf_size + flatbuffers::PaddingBytes(buf_size, byte_width) + elem_index * byte_width;
                    // Compute relative offset.
                    auto offset = offset_loc - u_;
                    // Does it fit?
                    auto bit_width = WidthU(offset);
                    if(static_cast<size_t>(static_cast<size_t>(1U) << bit_width) == byte_width)
                        return bit_width;
                }
                assert(false);    // Must match one of the sizes above.
                return BIT_WIDTH_64;
            }
        }

        BitWidth StoredWidth(BitWidth parent_bit_width_ = BIT_WIDTH_8) const
        {
            if(IsInline(type_))
            {
                return (std::max)(min_bit_width_, parent_bit_width_);
            }
            else
            {
                return min_bit_width_;
            }
        }
    };

    void WriteAny(const Value& val, uint8_t byte_width)
    {
        switch(val.type_)
        {
            case TYPE_NULL:
            case TYPE_INT:
                Write(val.i_, byte_width);
                break;
            case TYPE_BOOL:
            case TYPE_UINT:
                Write(val.u_, byte_width);
                break;
            case TYPE_FLOAT:
                WriteDouble(val.f_, byte_width);
                break;
            default:
                WriteOffset(val.u_, byte_width);
                break;
        }
    }

    size_t CreateBlob(const void* data, size_t len, size_t trailing, Type type)
    {
        auto bit_width = WidthU(len);
        auto byte_width = Align(bit_width);
        Write<uint64_t>(len, byte_width);
        auto sloc = buf_.size();
        WriteBytes(data, len + trailing);
        stack_.push_back(Value(static_cast<uint64_t>(sloc), type, bit_width));
        return sloc;
    }

    template <typename T> size_t ScalarVector(const T* elems, size_t len, bool fixed)
    {
        auto vector_type = GetScalarType<T>();
        auto byte_width = sizeof(T);
        auto bit_width = WidthB(byte_width);
        // If you get this assert, you're trying to write a vector with a size
        // field that is bigger than the scalars you're trying to write (e.g. a
        // byte vector > 255 elements). For such types, write a "blob" instead.
        // TODO: instead of asserting, could write vector with larger elements
        // instead, though that would be wasteful.
        assert(WidthU(len) <= bit_width);
        if(!fixed)
            Write<uint64_t>(len, byte_width);
        auto vloc = buf_.size();
        for(size_t i = 0; i < len; i++)
            Write(elems[i], byte_width);
        stack_.push_back(Value(static_cast<uint64_t>(vloc), ToTypedVector(vector_type, fixed ? len : 0), bit_width));
        return vloc;
    }

    Value CreateVector(size_t start, size_t vec_len, size_t step, bool typed, bool fixed, const Value* keys = nullptr)
    {
        // Figure out smallest bit width we can store this vector with.
        auto bit_width = (std::max)(force_min_bit_width_, WidthU(vec_len));
        auto prefix_elems = 1;
        if(keys)
        {
            // If this vector is part of a map, we will pre-fix an offset to the keys
            // to this vector.
            bit_width = (std::max)(bit_width, keys->ElemWidth(buf_.size(), 0));
            prefix_elems += 2;
        }
        Type vector_type = TYPE_KEY;
        // Check bit widths and types for all elements.
        for(size_t i = start; i < stack_.size(); i += step)
        {
            auto elem_width = stack_[i].ElemWidth(buf_.size(), i + prefix_elems);
            bit_width = (std::max)(bit_width, elem_width);
            if(typed)
            {
                if(i == start)
                {
                    vector_type = stack_[i].type_;
                }
                else
                {
                    // If you get this assert, you are writing a typed vector with
                    // elements that are not all the same type.
                    assert(vector_type == stack_[i].type_);
                }
            }
        }
        // If you get this assert, your fixed types are not one of:
        // Int / UInt / Float / Key.
        assert(IsTypedVectorElementType(vector_type));
        auto byte_width = Align(bit_width);
        // Write vector. First the keys width/offset if available, and size.
        if(keys)
        {
            WriteOffset(keys->u_, byte_width);
            Write<uint64_t>(1ULL << keys->min_bit_width_, byte_width);
        }
        if(!fixed)
            Write<uint64_t>(vec_len, byte_width);
        // Then the actual data.
        auto vloc = buf_.size();
        for(size_t i = start; i < stack_.size(); i += step)
        {
            WriteAny(stack_[i], byte_width);
        }
        // Then the types.
        if(!typed)
        {
            for(size_t i = start; i < stack_.size(); i += step)
            {
                buf_.push_back(stack_[i].StoredPackedType(bit_width));
            }
        }
        return Value(static_cast<uint64_t>(vloc),
                     keys ? TYPE_MAP : (typed ? ToTypedVector(vector_type, fixed ? vec_len : 0) : TYPE_VECTOR),
                     bit_width);
    }

    // You shouldn't really be copying instances of this class.
    Builder(const Builder&);
    Builder& operator=(const Builder&);

    std::vector<uint8_t> buf_;
    std::vector<Value> stack_;

    bool finished_;

    BuilderFlag flags_;

    BitWidth force_min_bit_width_;

    struct KeyOffsetCompare
    {
        KeyOffsetCompare(const std::vector<uint8_t>& buf) : buf_(&buf) {}
        bool operator()(size_t a, size_t b) const
        {
            auto stra = reinterpret_cast<const char*>(flatbuffers::vector_data(*buf_) + a);
            auto strb = reinterpret_cast<const char*>(flatbuffers::vector_data(*buf_) + b);
            return strcmp(stra, strb) < 0;
        }
        const std::vector<uint8_t>* buf_;
    };

    typedef std::pair<size_t, size_t> StringOffset;
    struct StringOffsetCompare
    {
        StringOffsetCompare(const std::vector<uint8_t>& buf) : buf_(&buf) {}
        bool operator()(const StringOffset& a, const StringOffset& b) const
        {
            auto stra = reinterpret_cast<const char*>(flatbuffers::vector_data(*buf_) + a.first);
            auto strb = reinterpret_cast<const char*>(flatbuffers::vector_data(*buf_) + b.first);
            return strncmp(stra, strb, (std::min)(a.second, b.second) + 1) < 0;
        }
        const std::vector<uint8_t>* buf_;
    };

    typedef std::set<size_t, KeyOffsetCompare> KeyOffsetMap;
    typedef std::set<StringOffset, StringOffsetCompare> StringOffsetMap;

    KeyOffsetMap key_pool;
    StringOffsetMap string_pool;
};

}    // namespace flexbuffers

#if defined(_MSC_VER)
#pragma warning(pop)
#endif

#endif    // FLATBUFFERS_FLEXBUFFERS_H_
